InforLorV4, Main, Exploration, bibRecord, 001358

On local search for bi-objective knapsack problems

Identifieur interne : 001358 ( Main/Exploration ); précédent : 001357; suivant : 001359

On local search for bi-objective knapsack problems

Auteurs : Arnaud Liefooghe [France] ; Luis Paquete [Portugal] ; José Figueira [Portugal]

Source :

Evolutionary Computation [ 1063-6560 ] ; 2013.

RBID : Hal:hal-00676625

Abstract

In this article, a local search approach is proposed for three variants of the bi-objective binary knapsack problem, with the aim of maximizing the total profit and minimizing the total weight. First, an experimental study on a given structural property of connectedness of the efficient set is conducted. Based on this property, a local search algorithm is proposed and its performance is compared against exact algorithms in terms of running time and quality metrics. The experimental results indicate that this simple local search algorithm is able to find a representative set of optimal solutions in most of the cases, and in much less time than exact algorithms.

Url:

https://hal.archives-ouvertes.fr/hal-00676625

DOI: 10.1162/EVCO_a_00074

Affiliations:

France, Portugal

Links toward previous steps (curation, corpus...)

to stream Hal, to step Corpus: 003722
to stream Hal, to step Curation: 003722
to stream Hal, to step Checkpoint: 001311
to stream Main, to step Merge: 001372
to stream Main, to step Curation: 001358

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">On local search for bi-objective knapsack problems</title>
<author><name sortKey="Liefooghe, Arnaud" sort="Liefooghe, Arnaud" uniqKey="Liefooghe A" first="Arnaud" last="Liefooghe">Arnaud Liefooghe</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-56013" status="OLD"><idno type="RNSR">200518286J</idno>
<orgName>Parallel Cooperative Multi-criteria Optimization</orgName>
<orgName type="acronym">DOLPHIN</orgName>
<date type="end">2014-12-31</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/dolphin</ref>
</desc>
<listRelation><relation active="#struct-2546" type="direct"></relation>
<relation active="#struct-301700" type="indirect"></relation>
<relation active="#struct-92973" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation name="UMR8022" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-104752" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-2546" type="direct"><org type="laboratory" xml:id="struct-2546" status="VALID"><orgName>Laboratoire d'Informatique Fondamentale de Lille</orgName>
<orgName type="acronym">LIFL</orgName>
<desc><address><addrLine>Bâtiment M3 59655 Villeneuve d'Ascq Cédex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.lifl.fr/</ref>
</desc>
<listRelation><relation active="#struct-301700" type="direct"></relation>
<relation active="#struct-92973" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation name="UMR8022" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-301700" type="indirect"><org type="institution" xml:id="struct-301700" status="VALID"><idno type="IdRef">026404524</idno>
<idno type="ISNI">0000000121517701</idno>
<orgName>Université de Lille, Sciences Humaines et Sociales</orgName>
<desc><address><addrLine>Domaine universitaire du "Pont de Bois"Rue du Barreau BP 60149 59653 Villeneuve d'Ascq Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lille3.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-92973" type="indirect"><org type="institution" xml:id="struct-92973" status="VALID"><idno type="IdRef">026404184</idno>
<orgName>Université de Lille, Sciences et Technologies</orgName>
<desc><address><addrLine>Cité Scientifique - 59655 Villeneuve d'Ascq Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lille1.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR8022" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-104752" type="direct"><org type="laboratory" xml:id="struct-104752" status="VALID"><idno type="RNSR">200818245B</idno>
<orgName>INRIA Lille - Nord Europe</orgName>
<desc><address><addrLine>Parc Scientifique de la Haute Borne 40, avenue Halley Bât.A, Park Plaza 59650 Villeneuve d'Ascq</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/lille/</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Paquete, Luis" sort="Paquete, Luis" uniqKey="Paquete L" first="Luis" last="Paquete">Luis Paquete</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-174702" status="VALID"><orgName>Evolutionary and Complex Systems Group</orgName>
<orgName type="acronym">ECOS Group</orgName>
<desc><address><addrLine>Coimbra</addrLine>
<country key="PT"></country>
</address>
</desc>
<listRelation><relation active="#struct-302036" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-302036" type="direct"><org type="institution" xml:id="struct-302036" status="VALID"><orgName>CISUC</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Portugal</country>
</affiliation>
</author>
<author><name sortKey="Figueira, Jose" sort="Figueira, Jose" uniqKey="Figueira J" first="José" last="Figueira">José Figueira</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-200504" status="VALID"><orgName>Center for Management Studies, Instituto Superior Técnico [Porto Salvo]</orgName>
<orgName type="acronym">CEG - IST</orgName>
<desc><address><addrLine>Tagus Park, Av. Cavaco Silva, 2780 - 990 Porto Salvo</addrLine>
<country key="PT"></country>
</address>
</desc>
<listRelation><relation active="#struct-368878" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-368878" type="direct"><org type="institution" xml:id="struct-368878" status="INCOMING"><orgName>Technical University of Lisbon</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Portugal</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00676625</idno>
<idno type="halId">hal-00676625</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-00676625</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00676625</idno>
<idno type="doi">10.1162/EVCO_a_00074</idno>
<date when="2013">2013</date>
<idno type="wicri:Area/Hal/Corpus">003722</idno>
<idno type="wicri:Area/Hal/Curation">003722</idno>
<idno type="wicri:Area/Hal/Checkpoint">001311</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">001311</idno>
<idno type="wicri:doubleKey">1063-6560:2013:Liefooghe A:on:local:search</idno>
<idno type="wicri:Area/Main/Merge">001372</idno>
<idno type="wicri:Area/Main/Curation">001358</idno>
<idno type="wicri:Area/Main/Exploration">001358</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">On local search for bi-objective knapsack problems</title>
<author><name sortKey="Liefooghe, Arnaud" sort="Liefooghe, Arnaud" uniqKey="Liefooghe A" first="Arnaud" last="Liefooghe">Arnaud Liefooghe</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-56013" status="OLD"><idno type="RNSR">200518286J</idno>
<orgName>Parallel Cooperative Multi-criteria Optimization</orgName>
<orgName type="acronym">DOLPHIN</orgName>
<date type="end">2014-12-31</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/dolphin</ref>
</desc>
<listRelation><relation active="#struct-2546" type="direct"></relation>
<relation active="#struct-301700" type="indirect"></relation>
<relation active="#struct-92973" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation name="UMR8022" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-104752" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-2546" type="direct"><org type="laboratory" xml:id="struct-2546" status="VALID"><orgName>Laboratoire d'Informatique Fondamentale de Lille</orgName>
<orgName type="acronym">LIFL</orgName>
<desc><address><addrLine>Bâtiment M3 59655 Villeneuve d'Ascq Cédex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.lifl.fr/</ref>
</desc>
<listRelation><relation active="#struct-301700" type="direct"></relation>
<relation active="#struct-92973" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation name="UMR8022" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-301700" type="indirect"><org type="institution" xml:id="struct-301700" status="VALID"><idno type="IdRef">026404524</idno>
<idno type="ISNI">0000000121517701</idno>
<orgName>Université de Lille, Sciences Humaines et Sociales</orgName>
<desc><address><addrLine>Domaine universitaire du "Pont de Bois"Rue du Barreau BP 60149 59653 Villeneuve d'Ascq Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lille3.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-92973" type="indirect"><org type="institution" xml:id="struct-92973" status="VALID"><idno type="IdRef">026404184</idno>
<orgName>Université de Lille, Sciences et Technologies</orgName>
<desc><address><addrLine>Cité Scientifique - 59655 Villeneuve d'Ascq Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lille1.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR8022" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-104752" type="direct"><org type="laboratory" xml:id="struct-104752" status="VALID"><idno type="RNSR">200818245B</idno>
<orgName>INRIA Lille - Nord Europe</orgName>
<desc><address><addrLine>Parc Scientifique de la Haute Borne 40, avenue Halley Bât.A, Park Plaza 59650 Villeneuve d'Ascq</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/lille/</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Paquete, Luis" sort="Paquete, Luis" uniqKey="Paquete L" first="Luis" last="Paquete">Luis Paquete</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-174702" status="VALID"><orgName>Evolutionary and Complex Systems Group</orgName>
<orgName type="acronym">ECOS Group</orgName>
<desc><address><addrLine>Coimbra</addrLine>
<country key="PT"></country>
</address>
</desc>
<listRelation><relation active="#struct-302036" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-302036" type="direct"><org type="institution" xml:id="struct-302036" status="VALID"><orgName>CISUC</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Portugal</country>
</affiliation>
</author>
<author><name sortKey="Figueira, Jose" sort="Figueira, Jose" uniqKey="Figueira J" first="José" last="Figueira">José Figueira</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-200504" status="VALID"><orgName>Center for Management Studies, Instituto Superior Técnico [Porto Salvo]</orgName>
<orgName type="acronym">CEG - IST</orgName>
<desc><address><addrLine>Tagus Park, Av. Cavaco Silva, 2780 - 990 Porto Salvo</addrLine>
<country key="PT"></country>
</address>
</desc>
<listRelation><relation active="#struct-368878" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-368878" type="direct"><org type="institution" xml:id="struct-368878" status="INCOMING"><orgName>Technical University of Lisbon</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Portugal</country>
</affiliation>
</author>
</analytic>
<idno type="DOI">10.1162/EVCO_a_00074</idno>
<series><title level="j">Evolutionary Computation</title>
<idno type="ISSN">1063-6560</idno>
<imprint><date type="datePub">2013</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">In this article, a local search approach is proposed for three variants of the bi-objective binary knapsack problem, with the aim of maximizing the total profit and minimizing the total weight. First, an experimental study on a given structural property of connectedness of the efficient set is conducted. Based on this property, a local search algorithm is proposed and its performance is compared against exact algorithms in terms of running time and quality metrics. The experimental results indicate that this simple local search algorithm is able to find a representative set of optimal solutions in most of the cases, and in much less time than exact algorithms.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>Portugal</li>
</country>
</list>
<tree><country name="France"><noRegion><name sortKey="Liefooghe, Arnaud" sort="Liefooghe, Arnaud" uniqKey="Liefooghe A" first="Arnaud" last="Liefooghe">Arnaud Liefooghe</name>
</noRegion>
</country>
<country name="Portugal"><noRegion><name sortKey="Paquete, Luis" sort="Paquete, Luis" uniqKey="Paquete L" first="Luis" last="Paquete">Luis Paquete</name>
</noRegion>
<name sortKey="Figueira, Jose" sort="Figueira, Jose" uniqKey="Figueira J" first="José" last="Figueira">José Figueira</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001358 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001358 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Hal:hal-00676625
   |texte=   On local search for bi-objective knapsack problems
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

On local search for bi-objective knapsack problems

On local search for bi-objective knapsack problems

Source :

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri